package leetcode.editor.vscdev;

import java.util.*;
import leetcode.editor.utils.*;

public class lc236 {
    /* 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
     * p q 一定存在，p！=q，且每个节点元素各不相同
     */
}
class Solution {
    // 递归回溯 采用后序遍历，左右中来实现从树底部进行处理
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 递归结束条件
        if (root == null||root == p || root == q) {
            return root;    
        }
        // 左
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        // 右
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // 中 处理
        if (left != null && right != null) {
            return root;
        } else if (left != null) {
            return left;
        } else {
            return right;
        }
    }
    // 迭代法 利用栈
    // TODO 二叉树最小公共祖先迭代法未完成
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> stack = new Stack<>();
        return null;
    }
}
